/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-26
 * Time: 23:45
 */
public class Main {
    public static void main(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet(10);
        System.out.println("合并：0和6：");
        unionFindSet.union(0,6);
        System.out.println("合并：0和7：");
        unionFindSet.union(0,7);
        System.out.println("合并：0和8：");
        unionFindSet.union(0,8);

        System.out.println("合并：1和4：");
        unionFindSet.union(1,4);
        System.out.println("合并：1和9：");
        unionFindSet.union(1,9);
        System.out.println("合并：2和3：");
        unionFindSet.union(2,3);
        System.out.println(unionFindSet.getCount());

        System.out.println("合并：2和5：");
        unionFindSet.union(2,5);
        System.out.println(unionFindSet.getCount());

        unionFindSet.print();
        System.out.println(unionFindSet.getCount());

        System.out.println("合并：8和1：");
        unionFindSet.union(8,1);

        unionFindSet.print();

        System.out.println("查找是不是同一个集合");
        System.out.println(unionFindSet.isSameUnionFindSet(6, 9));
        System.out.println(unionFindSet.isSameUnionFindSet(8, 2));
        System.out.println(unionFindSet.getCount());
    }



    // leetcode 547. 省份数量
    public int findCircleNum(int[][] isConnected) {
        int count=0;
        int length=isConnected.length;
        UnionFindSet unionFindSet = new UnionFindSet(length);
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < isConnected[i].length; j++) {
                unionFindSet.union(i, j);
            }
        }

        return unionFindSet.getCount();
    }


    // leetcode 990. 等式方程的可满足性
    public boolean equationsPossible(String[] equations) {
        int length=equations.length;
        UnionFindSet unionFindSet=new UnionFindSet(26);
        // 先将所有等于的合并
        for (String temp : equations) {
            if (temp.charAt(1) == '=') {
//               是 ==
                unionFindSet.union(temp.charAt(0) - 'a', temp.charAt(3) - 'a');
            }
        }


        // 再将所有不等于进行判定是否满足条件
        for (String temp : equations) {
            if (temp.charAt(1) == '!') {
//               是 !=
                if(unionFindSet.isSameUnionFindSet(temp.charAt(0)-'a',temp.charAt(3)-'a')){
                    // 是一个集合里面的
                    return false;
                }
            }
        }
        return true;
    }
}
